package com.mdnote.practice.dp;

import java.util.Arrays;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/21
 * @description 打家劫舍
 */
public class LeetCode198 {


    public static void main(String[] args) {
        LeetCode198 leetCode198 = new LeetCode198();
        int res = leetCode198.rob(new int[]{2,7,9,3,1});
        System.out.println(res);
    }
    public int rob(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        // DP
        return dp(nums);
    }

    /**
     * 分析：1. 重复子问题：
     *      2. DP[U][0]  必偷第i个房间可以获得的最大利润
     *         dp[i][1]  不偷第i个房间可以获得最大丽人
     *      3. DP公式
     *          dp[i][0] = z[i - 1][1] + num[i]
     *          dp[i][1] = Max(dp[i - 1][1], dp[i - 1][0])
     * @param nums
     * @return
     */
    private int dp(int[] nums) {

        // 初始化DP
        int[][] dp = new int[nums.length][2];
        dp[0][0] = nums[0];

        for (int i = 1; i < dp.length; i++) {
            dp[i][0] = nums[i] + dp[i - 1][1];
            dp[i][1] = Math.max(dp[i - 1][0],  dp[i - 1][1]);
        }

        return Math.max(dp[dp.length - 1][0], dp[dp.length - 1][1]);
    }

    private int dpPlus(int[] nums) {

        // 初始化DP
        int dp0 = nums[0];
        int dp1 = 0;

        for (int i = 1; i < nums.length; i++) {
           int dp_t = dp0, dp_u = dp1;
           dp0 = dp_u + nums[i];
           dp1 = Math.max(dp_t, dp_u);
        }

        return Math.max(dp0, dp1);
    }
}
